1. Field of the Invention
The present invention relates in general to a bilinear decimator for reducing the vertical resolution of a pixel-based image and in particular to a decimator which compensates for aliasing errors.
2. Description of Related Art
An image formed by a set of N parallel lines of L pixels each may be represented by a matrix of pixel data values. Each pixel data value X(n,h) represents a visual characteristic (such as intensity or chroma) of the lth pixel of the nth line of the image. Since various standard video formats have differing numbers of lines, a pixel data matrix suitable for one video format may not be suitable for another. For example one computer video standard employs 768 lines and one television video format employs 400 lines. Although an image on the television may be the same size as an image on the computer screen, it has lower resolution in the vertical direction.
It is sometimes desirable to display image on one video system in response to a pixel data matrix generated by another. One of the problems associated with doing that is adjusting the size of the data matrix representing the image to match the standard of the video system that is to display the image. For example, in order to convert a pixel data matrix having 786 rows of data (one for each line of the computer video image) to a pixel data matrix having 400 rows of data (one for each line of the television image) we have to reduce the number of rows of data in the matrix. One method of doing that is simply to throw out the extra 386 rows of data. Depending on which rows of data we throw out, this would have the effect of clipping a part of the image when it is displayed. To retain some semblance of the full image on the television screen we could remove (decimate) rows of data in an distributed manner so that every second or third line of the image would be remove. However such an image would somewhat distorted because all of the information contained in decimated lines would be lost and the information contained in the retained lines would be over represented in the television image.
For example, suppose a high resolution image produces a certain shade of gray in an area of the image by vertically alternating black and white pixels. If we reduce resolution of the image, for example, by 50% by removing every other line of the image, the gray area in the lower resolution image will appear either all white or all black. This error condition arises because the decimation pattern matches a pixel pattern in the image. Such an error condition is called "aliasing".
U.S. Pat. No. 5,469,222 issued Nov. 21, 1995 to Sprague discloses a decimating filter for lowering the vertical resolution of an image through a process of interpolation. If we superimpose high and low vertical resolution versions of the same image, each pixel of the lower resolution image will fall between vertically adjacent pixels of the higher resolution image. Sprague's filter computes the value of each pixel of the lower resolution image as a weighted sum of the two vertically adjacent pixels of the higher resolution image. The weights are inversely proportional the distance between the output pixel and the adjacent pixels of the input image. Thus for example when reducing the resolution of an image by 50%, instead of throwing out every other pixel line, Sprague's filter produces one output image line for each pair of input image lines, where the intensity or color of a pixel of the output image line is the average intensity or color of vertically adjacent pixels of the two input lines. Since all of the data of the high resolution image has an equal influence on the low resolution image, the lower resolution image is less subject to aliasing errors than if it were produced by simply throwing out every other line of the high resolution image.
The decimation ratio P/N of a filter is the number (P) of lines in the low resolution image divided by the total number of lines (N) of the high resolution image. Sprague's filter employs fixed weighting factors for a given decimation ratio. That means that the relative position of each pixel of the output image is fixed in relation to its vertically adjacent neighbors and does not change from line to line. This is only true for decimation ratios that reduce to the form 1--(1/n) where n is an integer. Thus Sprague's decimator can decimate by a factor of 1/2, 3/4, 7/8 . . . 1--(1/n). It cannot, for example, turn a 768 line image into a 400 line image because it is not capable of producing a decimation ratio of 368/768 (25/48).
U.S. Pat. No. 5,253,041 issued Oct. 12, 1993 to Wine et al, U.S. Pat. No. 4,204,227 issued May 20, 1980 to Gurley, and U.S. Pat. No. 5,159,451 issued Oct. 27, 1992 to Faroudja et al all disclose decimators which use fixed weighting factors for computing pixel values and are thus restricted to decimation ratios of the form 1--(1/n).
U.S. Pat. No. 5,019,904 issued May 28, 1991 to Campbell discloses a decimating filter which uses a lookup table to provide weighting factors that are functions of relative position of an output image pixels with respect to nearby pixels of the input image. Thus a pixel in any given line of the lower resolution output image is not restricted to a particular position with respect to vertically adjacent pixels of the higher resolution input image. Lacking such restriction, Campbell's weighting factor lookup table can be programmed to provide any vertical decimation ratio of the form P/N where P and N are integers. Thus Campbell's system is capable of implementing the 368/768 decimation ratio needed to lower the vertical resolution of the 768 line computer image to the 400 lines of television image.
To further reduce the likelihood of aliasing errors, Campbell's system uses data from the six vertically nearest pixels of the high resolution image, rather than two. Thus each output pixel data value is a weighted sum of contributions from six vertically adjacent pixels of the input image. The two high resolution image pixels nearest the low resolution image pixel are given more weight the remaining four. This reduces aliasing errors. One problem with Campbell's decimator is its size and cost. With six weighting factors, Campbell's system requires six multipliers. Multipliers require a lot space on an integrated circuit and are therefore expensive.
All prior art decimating systems which compute output pixel values as weighted combinations of values of N vertically adjacent input pixels require the use of at least N multipliers in order to apply the weights to the input pixels. Some system employ even more than N multipliers. U.S. Pat. No. 5,268,751 issued Dec. 7, 1993 to Geiger et al describes a polyphase FIR filter apparently employing fifteen fixed coefficients to produce a low resolution pixel as a weighted combination of 4 vertically adjacent high resolution pixels. However since the weighting factors are fixed, Geigher's system is restricted to a decimation ratio of 1--(1/n).
What is needed is a vertical decimation filter providing any desired decimation ratio of the form P/N (where P and N are integers P&lt;N) but which minimizes aliasing errors when necessary without employing excessive numbers of multipliers.